package com.zjj.algorithm.learning.leetcode.linkedlist;

/**
 * 学习链表逆序
 *
 * @author zjj_admin
 * @date 2022/11/18 16:29
 */
public class ReverseList {

    public static void main(String[] args) {
        ListNode node6 = new ListNode(4, null);
        ListNode node7 = new ListNode(3, node6);
        ListNode node8 = new ListNode(2, node7);
        ListNode node9 = new ListNode(1, node8);

        reverseList1(node9);
    }


    /**
     * 剑指 Offer II 024. 反转链表 简单题
     * 给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 41 MB
     * 击败
     * 90.5%
     * 方法 1：
     *
     * @param head
     */
    public static ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        //定义一个curr节点指向head的next节点，每一次反转都是将curr节点移动到头结点位置
        ListNode curr = head.next;
        //定义next节点，目的是为了记录当前节点的下一个节点
        ListNode next;
        while (curr != null) {
            //让next节点指向下一个需要移动的节点
            next = curr.next;
            //删除head节点的后一个节点 head.next = head.next.next; 和 head.next = next; 等价
            head.next = head.next.next;
            //让当前节点的next节点指向头结点
            curr.next = dummy.next;
            //让虚拟头结点的next节点指向当前节点
            dummy.next = curr;
            //让当前节点指向原来的下一个节点，即next节点
            curr = next;
        }
        return dummy.next;
    }
}
